package cn.fxzhang.leetcode.no00;

import cn.fxzhang.leetcode.common.ListNode;

/**
 * 2.两数相加
 * 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字
 * 请你将两个数相加，并以相同形式返回一个表示和的链表。
 *
 * 类型：链表
 * 题解：基本链表操作
 * 时间复杂度：O(N), N是数组中的元素数量
 * 空间复杂度：O(N)
 *
 * 提交记录(1/2)
 * 执行用时: 2 ms，击败了100.00%
 * 内存消耗: 38.9 MB，击败了40.14%
 *
 * 【中等】通过次数773,815提交次数1,942,694
 * @author 张晓帆
 * @date 2021/3/29
 */
public class P0002_Add_Two_Numbers {

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 空头部
        ListNode head = new ListNode(0);
        // 当前位置
        ListNode current = head;
        // 加数
        int a = l1.val;
        int b = l2.val;
        // c表示进位，0或1
        int c = 0;
        do{
            int sum = a + b + c;
            c = sum / 10;
            ListNode next = new ListNode(sum % 10);
            current.next = next;
            current = next;
            // 移动位置
            if (l1.next != null){
                l1 = l1.next;
                a = l1.val;
            } else {
                a = 0;
            }
            if (l2.next != null){
                l2 = l2.next;
                b = l2.val;
            } else {
                b = 0;
            }
        } while (l1.next != null || l2.next != null || a+b+c > 0);
        return head.next;
    }
}
